#include <iostream>
#include <vector>
using namespace std;

//交换法:在新数字插入过程中，不断与前面的数字交换，直到找到自己合适的位置
void InsertSort1 (vector<int>& v) {
	int len = v.size();
	for(int i = 1; i < len; i++) {
		int j = i;
		while(j >= 1 && v[j] < v[j-1])
		{
			swap(v[j - 1], v[j]);
			j--;
		}	
	}
}

//移动法:在新数字插入过程中，与前面的数字不断比较，前面的数字不断向后挪出位置，当新数字找到自己的位置后，插入一次即可。
void InsertSort2 (vector<int>& v) {
	int len = v.size();
	for(int i = 1; i < len; i++) {
		int cur = v[i];
		int j = i - 1;
		while(j >= 0 && cur < v[j]) {
			v[j+1] = v[j];
			j--;
		}
		v[j+1] = cur;
	}
}


int main() {
	vector<int> v{1,4,3,2,7,9,5,0,4,10,6,3};
	for(auto& t : v)
		cout << t << " ";
	cout << endl;
	
	//InsertSort1(v);
	InsertSort2(v);
	
	for(auto& t : v)
		cout << t << " ";
	cout << endl;
	return 0;
}

/*
发个不稳定算法的口诀
8种常见排序中（快排、希尔、堆排、归并、冒泡、选择、插入、基数排序）
快些（希尔）选堆不稳定，剩下的稳定
*/